Research on Multiple Input Multiple Output (MIMO) technologies, which constitute a part of the next generation communication technologies, has been actively performed in these years. In a MIMO system, a transmitter having multiple transmitting antennas transmits multiple data streams, and a receiver having multiple receiving antennas separates and receives the multiple data streams.
FIG. 1 illustrates an exemplary MIMO system.
In FIG. 1, a transmitter includes M transmitting antennas and a receiver includes N receiving antennas. In this example, for brevity, it is assumed that the transmitter transmits M data streams that correspond to the number of transmitting antennas. It is also assumed that M≦N, and the receiver receives N signals. The received signals are represented by formula (1) below where a vector x with M rows and one column indicates the data streams, H indicates a channel matrix including N rows and M columns of elements each indicating a propagation path gain hij between a j-th transmitting antenna and an i-th receiving antenna, a vector y with N rows and one column indicates the received signals, and a vector n with N rows and one column indicates noise.
                                              ⁢                  y          =                                    Hx              +                              n                ⁢                                                                  (                                                                                                    y                        0                                                                                                                                                y                        1                                                                                                                        ⋮                                                                                                                          y                                                  N                          -                          1                                                                                                                    )                                      =                                                            (                                                                                                              h                          00                                                                                                                      h                          01                                                                                            …                                                                                              h                                                      0                            ,                                                          M                              -                              1                                                                                                                                                                                                                    h                          10                                                                                                                      h                          11                                                                                            …                                                                                              h                                                      1                            ,                                                          M                              -                              1                                                                                                                                                                                          ⋮                                                                    ⋮                                                                    ⋱                                                                    ⋮                                                                                                                                      h                                                                                    N                              -                              1                                                        ,                            0                                                                                                                                                h                                                                                    N                              -                              1                                                        ,                            1                                                                                                                      …                                                                                              h                                                                                    N                              -                              1                                                        ,                                                          M                              -                              1                                                                                                                                                            )                                ⁢                                  (                                                                                                              x                          0                                                                                                                                                              x                          1                                                                                                                                    ⋮                                                                                                                                      x                                                      M                            -                            1                                                                                                                                )                                            +                              (                                                                                                    n                        0                                                                                                                                                n                        1                                                                                                                        ⋮                                                                                                                          n                                                  N                          -                          1                                                                                                                    )                                                                        (        1        )            
Known stream separation methods at the receiving end include Minimum Mean Square Error (MMSE) and Maximum Likelihood Detection (MLD).
In MLD, metrics such as squared Euclidean distances are calculated for all combinations of symbol replica candidates of stream signals, and one of the combinations with the smallest total metric is selected as separated stream signals. Compared with a linear separation method such as MMSE, MLD provides excellent reception characteristics. Here, when ml indicates a modulation level (e.g., m=4 for QPSK, m=16 for 16 QAM, and m=64 for 64 QAM) of a first transmission signal, the number of combinations is represented by formula (2) below.
                              ∏                      k            =            1                    M                ⁢                  m          k                                    (        2        )            
According to formula (2), the number of metric calculations increases exponentially as the number of modulation levels and the number of transmission streams increase and as a result, the processing load increases drastically. For this reason, various types of MLD methods that can reduce the number of calculations have been proposed.
For example, QRM-MLD based on a combination of QR decomposition and M algorithm is known (see, for example, K. J. Kim and J. Yue, “Joint channel estimation and data detection algorithms for MIMO-OFDM systems,” in Proc. Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, pp. 1857-1861, November 2002). In QRM-MLD, metrics such as squared Euclidean distances between all symbol replica candidates and surviving symbol replica candidates of the previous stage are calculated. When Sk indicates the number of surviving candidates of a k-th stage (k=1 through M), the number of metric calculations is represented by formula (3) below.
                              S          1                +                              ∑                          k              =              2                        M                    ⁢                                    m              k                        ⁢                          S                              k                -                1                                                                        (        3        )            
The adaptive selection of surviving symbol replica candidates based on maximum reliability (ASESS) is also known (see, for example, K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection of Surviving Symbol Replica Candidates Based on Maximum Reliability in QRM-MLD for OFCDM MIMO Multiplexing,” Proc. of IEEE Globecom 2004, pp. 2480-2486, November 2004; and Higuchi, Kawai, Maeda and Sawahashi, “Adaptive Selection Algorithm of Surviving Symbol Replica Candidates in QRM-MLD for MIMO Multiplexing Using OFCDM Wireless Access,” RCS2004-69, May 2004). ASESS is a variation of QRM-MLD and designed to further reduce the number of metric calculations. In the ASESS method, symbol replica candidates in each stage are ranked by region detection, and metrics corresponding to the number of surviving symbol replica candidates are calculated for symbol replicas in ascending order of cumulative metric values. When Sk indicates the number of surviving candidates of the k-th stage (k=1 through M), the number of metric calculations is represented by formula (4) below.
                              ∑                      k            =            1                    M                ⁢                  S          k                                    (        4        )            
According to the ASESS method, the number of metric calculations linearly increases as the number of transmission streams increases.
There also exists a variation of List Sphere Decoding (LSD) where a method of ranking symbol candidates is employed.
The ASESS method is described in more detail below. In the descriptions below, for brevity, it is assumed that M=N. Formula (5) is obtained by decomposing a channel matrix H into a unitary matrix Q and an upper triangular matrix R.
                    H        =                  QR          =                                    (                                                                                          q                      00                                                                                                  q                      01                                                                            …                                                                              q                                              0                        ,                                                  N                          -                          1                                                                                                                                                                                q                      10                                                                                                  q                      11                                                                            …                                                                              q                                              1                        ,                                                  N                          -                          1                                                                                                                                                          ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                              q                                                                        N                          -                          1                                                ,                        0                                                                                                                        q                                                                        N                          -                          1                                                ,                        1                                                                                                  …                                                                              q                                                                        N                          -                          1                                                ,                                                  N                          -                          1                                                                                                                                )                        ⁢                          (                                                                                          r                      00                                                                                                  r                      01                                                                            …                                                                              r                                              0                        ,                                                  N                          -                          1                                                                                                                                                                                                                                                                                  r                      11                                                                            …                                                                              r                                              1                        ,                                                  N                          -                          1                                                                                                                                                          O                                                                                                                                                          ⋱                                                        ⋮                                                                                                                                                                                                                                                                                                                                                                                                                    r                                                                        N                          -                          1                                                ,                                                  N                          -                          1                                                                                                                                )                                                          (        5        )            
In formula (5), 0 indicates a null matrix. That is, 0 indicates that matrix elements are zero. “Elements” may also be referred to as “components”. Received signals y can be orthogonalized as indicated by formula (6) by multiplying the received signals y by the Hermitian conjugate of the unitary matrix Q from the left.
                    z        =                                            Q              H                        ⁢            y                    =                                                                      Q                  H                                ⁢                QRx                            +                                                Q                  H                                ⁢                n                                      =                                          Rx                +                                                      n                    ′                                    ⁢                                                                          (                                                                                                              z                          0                                                                                                                                                              z                          1                                                                                                                                    ⋮                                                                                                                                      z                                                      N                            -                            1                                                                                                                                )                                            =                                                                    (                                                                                                                        r                            00                                                                                                                                r                            01                                                                                                    …                                                                                                      r                                                          0                              ,                                                              N                                -                                1                                                                                                                                                                                                                                                                                                                                                                      r                            11                                                                                                    …                                                                                                      r                                                          1                              ,                                                              N                                -                                1                                                                                                                                                                                                          O                                                                                                                                                                                                          ⋱                                                                          ⋮                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  r                                                                                          N                                -                                1                                                            ,                                                              N                                -                                1                                                                                                                                                                          )                                    ⁢                                      (                                                                                                                        x                            0                                                                                                                                                                            x                            1                                                                                                                                                ⋮                                                                                                                                                  x                                                          N                              -                              1                                                                                                                                            )                                                  +                                  (                                                                                                              n                          0                          ′                                                                                                                                                              n                          1                          ′                                                                                                                                    ⋮                                                                                                                                      n                                                      N                            -                            1                                                    ′                                                                                                      )                                                                                        (        6        )            
In a first stage, for the last row, region detection is performed for uN-1=zN-1/rN-1,N-1 and a region number ε(1) of a region to which uN-1 belongs is determined. In the region detection, quadrant detection is performed Ndiv times, origin shift is performed Ndiv−1 times, and one of 22Ndiv regions is determined. Top S1 replica candidates (S1 indicates the number of surviving candidates) in a symbol ranking table Ω are selected as surviving paths of the first stage, and metrics such as squared Euclidean distances are calculated for the surviving paths. The surviving paths are represented by formula (7) below.Π1(1)(i)=Ω(mN)(ε,i)  (7)
When squared Euclidean distances are used as metrics, formula (8) is obtained.d1(i)=|zN-1−rN-1,N-1cN-1,Π1(1)(i)|2, i=0,1, . . . ,S1−1  (8)
Here, Ω(4), Ω(16), and Ω(64) indicate symbol ranking tables for QPSK, 16QAM, and 64QAM, respectively. Ω(mN)(ε(l),i) indicates a symbol number of an i-th ranked symbol stored in the symbol ranking table and corresponding to the region number ε(l).
In a second stage, the Sl replica candidates selected as the surviving paths in the first stage are cancelled from the second last received signal zN-2 as indicated by formula (9), the result of formula (9) is divided by the second last diagonal component of the upper triangular matrix R as indicated by formula (10), and region detection is performed for the result of formula (10). That is, a region number ε(2)(i) of a region to which uN-2(i) belongs is determined.z′N-2(i)=zN-2−rN-2,N-1cN-2,Π1(1)(i), i=0,1, . . . ,S1−1  (9)uN-2(i)=z′N-2(i)/rN-2,N-2, i=0,1, . . . ,S1−1  (10)
Surviving paths of the second stage are adaptively selected as described below. A representative metric value E(i) and a current rank ρ(i) of each surviving path of the first stage are initialized. As a result, formula (11) is obtained.
                                                                                          E                  ⁡                                      (                    i                    )                                                  :=                                                      d                    1                                    ⁡                                      (                    i                    )                                                                                                                                            ρ                  ⁡                                      (                    i                    )                                                  :=                0                                                                                        q                :=                0                                                    }                            (        11        )            
A replica candidate ranked ρ(imin)-th (imin is a value that satisfies ρ(i)<mN-2 and min[E(i)]) is selected from the symbol ranking table, and a q-th surviving path of the second stage is determined as indicated by formula (12).
                                                                                                                                    ∏                      1                                                              (                      2                      )                                                        ⁢                                      (                    q                    )                                                  =                                                      ∏                    1                                          (                      1                      )                                                        ⁢                                                                          ⁢                                      (                                          i                      min                                        )                                                                                                                                                                                      ∏                      2                                                              (                      2                      )                                                        ⁢                                      (                    q                    )                                                  =                                                      Ω                                          (                                              m                                                  N                          -                          1                                                                    )                                                        ⁡                                      (                                                                                                                        ɛ                                                          (                              2                              )                                                                                ⁡                                                      (                                                          i                              min                                                        )                                                                          ,                                            ⁣                                              ρ                        ⁡                                                  (                                                      i                            min                                                    )                                                                                      )                                                                                                                                            i                  min                                =                                                      arg                                                                  ρ                        ⁡                                                  (                          i                          )                                                                    <                                              m                                                  N                          -                          2                                                                                                      ⁡                                      (                                          min                      ⁡                                              [                                                  E                          ⁡                                                      (                            i                            )                                                                          ]                                                              )                                                                                      }                            (        12        )            
A cumulative metric is calculated. Formula (13) is obtained.d2(q)=d1(imin)+|z′N-2(imin)−rN-2,N-2cN-2,Π2(2)(q)|2  (13)
Then, according to formula (14), the representative metric value and the current rank are updated.
                                                                                          E                  ⁡                                      (                                          i                      min                                        )                                                  :=                                                      d                    2                                    ⁡                                      (                    q                    )                                                                                                                                            ρ                  ⁡                                      (                                          i                      min                                        )                                                  :=                                                      ρ                    ⁡                                          (                                              i                        min                                            )                                                        +                  1                                                                                                        q                :=                                  q                  +                  1                                                                    }                            (        14        )            
The above process is repeated until “q” reaches the number of surviving paths S2 of the second stage.
In a subsequent k-th stage, Sk-1 replica candidates selected as the surviving paths in the (k−1)th stage are cancelled from the k-th received signal zN-k from the last as indicated by formula (15).
                                                        z                              N                -                k                            ′                        ⁡                          (              i              )                                =                                    z                              N                -                k                                      -                                          ∑                                  p                  =                  1                                                  k                  -                  1                                            ⁢                                                r                                                            N                      -                      k                      +                      1                                        ,                                          N                      -                      p                      +                      1                                                                      ⁢                                  c                                                            N                      -                      p                      +                      1                                        ,                                                                  ∏                        p                                                  (                                                      k                            -                            1                                                    )                                                                    ⁢                                              (                        i                        )                                                                                                                                ,                                  ⁢                  i          =          0                ,        1        ,        …        ⁢                                  ,                              S                          k              -              1                                -          1                                    (        15        )            
Region detection is performed for uN-k(i)=z′N-k(i)/rN-k,N-k (i=0, 1, . . . , Sk-1−1), which is obtained by dividing the result of formula (15) by the k-th diagonal component from the last of the upper triangular matrix R, and a region number ε(k)(i) to which uN-k(i) belongs is determined. Surviving paths of the k-th stage are adaptively selected as described below. A representative metric value E(i) and a current rank ρ(i) of each surviving path of the (k−1)th stage are initialized. Formula (16) is obtained.
                                                                                          E                  ⁡                                      (                    i                    )                                                  :=                                                      d                                          k                      -                      1                                                        ⁡                                      (                    i                    )                                                                                                                                            ρ                  ⁡                                      (                    i                    )                                                  :=                1                                                                                        q                :=                1                                                    }                            (        16        )            
A replica candidate ranked ρ(imin)-th (imin is a value that satisfies ρ(i)≦mN-k and min[E(i)]) is selected from the symbol ranking table. The q-th surviving path of the k-th stage is represented by formula (17).
                                                                                                                                    ∏                                              1                        -                        k                        -                        1                                                                                    (                      k                      )                                                        ⁢                                      (                    q                    )                                                  =                                                      ∏                                          (                                              k                        -                        1                                            )                                                        ⁢                                      (                                          i                      min                                        )                                                                                                                                                                                      ∏                      k                                                              (                      k                      )                                                        ⁢                                      (                    q                    )                                                  =                                                      Ω                                          (                                              m                                                  N                          -                          k                                                                    )                                                        ⁡                                      (                                                                                                                        ɛ                                                          (                              k                              )                                                                                ⁡                                                      (                                                          i                              min                                                        )                                                                          ,                                            ⁣                                              ρ                        ⁡                                                  (                                                      i                            min                                                    )                                                                                      )                                                                                                                                            i                  min                                =                                                      arg                                                                  ρ                        ⁡                                                  (                          i                          )                                                                    <                                              m                                                  N                          -                          k                                                                                                      ⁡                                      (                                          min                      ⁡                                              [                                                  E                          ⁡                                                      (                            i                            )                                                                          ]                                                              )                                                                                      }                            (        17        )            
A cumulative metric is calculated and formula (18) is obtained.dk(q)=dk-1(imin)+|z′N-k(imin)−rN-k,N-kcN-k,Πk(k)(q)|2  (18)
Then, according to formula (19), the representative metric value and the current rank are updated.
                                                                                          E                  ⁡                                      (                                          i                      min                                        )                                                  :=                                                      d                    k                                    ⁡                                      (                                                                  ∏                                                  (                          k                          )                                                                    ⁢                                              (                        q                        )                                                              )                                                                                                                                            ρ                  ⁡                                      (                                          i                      min                                        )                                                  :=                                                      ρ                    ⁡                                          (                                              i                        min                                            )                                                        +                  1                                                                                                        q                :=                                  q                  +                  1                                                                    }                            (        19        )            
The above process is repeated until “q” reaches the number of surviving paths Sk of the k-th stage.
Processes are performed up to the N-th stage, and surviving paths with the smallest cumulative metric dN are determined as a combination of most-likely symbols. When the signal is error-correction encoded, a log likelihood ratio (LLR) is calculated.